import java.util.Arrays;

/**
 * @author ChenJunhong
 * @date 2018/11/03
 * Description:
 * 快速排序，其基本的思路就是选取一个枢纽值，将数组中剩余的元素与该值进行比较。由此得到一个有序的序列。
 * 选取枢纽值pivot的依据有以下几种：
 * 1、 固定选取第一个元素
 * 2、 固定选取最后一个元素
 * 3、 随机选取一个元素
 */
public class QuickSort {
    /**
     * 快速排序算法，本代码中使用数组中的最后一个元素作为pivot
     * @param arr
     */
    public static void quickSort(int[] arr){
        sort(arr,0,arr.length-1);
    }

    public static void sort(int[] arr, int left, int right){
        if (left < right){
            int pivot = partition(arr,left,right);
            sort(arr,left,pivot-1);
            sort(arr,pivot+1,right);
        }

    }

    /**
     * 此方法的目的有三个：
     * 1、 将比pivot值小的数字放在其前面
     * 2、 将比pivot值大的数字放在其后面
     * 3、 将pivot放在数组中正确的位置
     * 注意： 此处选择pivot的值为数组最后一个数字
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] arr, int left, int right) {

        int pivot = arr[right];
        // 存放较小数字的索引
        int i = left - 1;
        for (int j = left; j <= right - 1 ; j++) {
            // 如果数字小于pivot，交换i j两个位置的值
            if(arr[j] <= pivot){
                i++;
                swap(arr,i,j);
            }
        }

        // 第i个数字存放的数字永远小于pivot，因此将i+1的值设置为pivot
        // 这样就可以保证pivot将数组分为了两个部分，前半部分都小于pivot，后半部分都大于pivot
        swap(arr,i+1,right);
        return i+1;
    }

    /**
     * 交换数组中的数据的位子
     * @param arr
     * @param x
     * @param y
     */
    public static void swap(int[] arr, int x, int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {34,5,6,3,1,8};
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
